package com.mango.leet.code.easy;

/**
 * 剑指 Offer 10- I. 斐波那契数列
 * @Author: mango
 * @Date: 2022/5/1 10:06 下午
 */

import java.util.HashMap;
import java.util.Map;

/**
 * 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
 *
 * F(0) = 0,   F(1) = 1
 * F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
 * 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
 *
 * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 2
 * 输出：1
 * 示例 2：
 *
 * 输入：n = 5
 * 输出：5
 *  
 *
 * 提示：
 *
 * 0 <= n <= 100
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LCOffer10 {
    public static void main(String[] args) {
        System.out.println(new Solution().fib(411));
    }

    static class Solution {

        public int fib(int n) {
            Map<Integer,Integer> map = new HashMap<>();
            int a =  process(n,map);
            return a;
        }

        private int process(int n,Map<Integer,Integer> map) {
            if(n == 0){
                return 0;
            }
            if(n == 1){
                return 1;
            }
            if(n>2){
                map.remove(n-1);
            }
            if(map.containsKey(n)){
                return map.get(n);
            }
            int result = process(n-1,map) + process(n-2,map);
            result %= 1000000007;
            map.put(n,result);
            return result;
        }
    }
}
